#include <vector>

using namespace std;

// 水资源分配优化
// 村里面一共有 n 栋房子。我们希望通过建造水井和铺设管道来为所有房子供水。
// 对于每个房子 i，我们有两种可选的供水方案：一种是直接在房子内建造水井
// 成本为 wells[i - 1] （注意 -1 ，因为 索引从0开始 ）
// 另一种是从另一口井铺设管道引水，数组 pipes 给出了在房子间铺设管道的成本，
// 其中每个 pipes[j] = [house1j, house2j, costj] 
// 代表用管道将 house1j 和 house2j连接在一起的成本。连接是双向的。
// 请返回 为所有房子都供水的最低总成本
// 测试链接 : https://leetcode.cn/problems/optimize-water-distribution-in-a-village/

class Solution 
{
private:
    static const int MAXN = 10010;
    tuple<int, int, int> edges[MAXN << 1];
    int cnt;
    int father[MAXN];

    void Build(int n)
    {
        cnt = 0;
        for(int i = 0; i <= n; ++i)
        {
            father[i] = i;
        }
    }

    int Find(int i)
    {
        return i == father[i] ? i : father[i] = Find(father[i]);
    }

    // 如果 x 和 y，原本是一个集合，返回 false
    // 如果 x 和 y，不是一个集合，合并之后后返回 true
    bool Union(int x, int y)
    {
        int fx = Find(x);
        int fy = Find(y);
        if(fx != fy)
        {
            father[fx] = fy;
            return true;
        }
        return false;
    }

public:
    int minCostToSupplyWater(int n, vector<int>& wells, vector<vector<int>>& pipes) 
    {
        Build(n);
        for(int i = 0; i < n; ++i, ++cnt)
        {
            // 建立 0 -> i + 1 这条虚拟的边 
            edges[cnt] = {wells[i], 0, i + 1};
        }

        for(int i = 0; i < pipes.size(); ++i, ++cnt)
        {
            edges[cnt] = {pipes[i][2], pipes[i][0], pipes[i][1]};
        }

        // 跑 Kruskal 算法
        sort(edges, edges + cnt);
        int ans = 0;
        for(int i = 0; i < cnt; ++i)
        {
            if(Union(get<1>(edges[i]), get<2>(edges[i])))
            {
                ans += get<0>(edges[i]);
            }
        }
        return ans;
    }
};


class Solution 
{
private:
    static const int MAXN = 10010;
    vector<tuple<int, int, int>> edges;
    int cnt;
    int father[MAXN];

    void Build(int n)
    {
        cnt = 0;
        edges.resize(MAXN << 1);
        for(int i = 0; i <= n; ++i)
        {
            father[i] = i;
        }
    }

    int Find(int i)
    {
        return i == father[i] ? i : father[i] = Find(father[i]);
    }

    // 如果 x 和 y，原本是一个集合，返回 false
    // 如果 x 和 y，不是一个集合，合并之后后返回 true
    bool Union(int x, int y)
    {
        int fx = Find(x);
        int fy = Find(y);
        if(fx != fy)
        {
            father[fx] = fy;
            return true;
        }
        return false;
    }

public:
    int minCostToSupplyWater(int n, vector<int>& wells, vector<vector<int>>& pipes) 
    {
        Build(n);
        for(int i = 0; i < n; ++i, ++cnt)
        {
            // 建立 0 -> i + 1 这条虚拟的边 
            edges[cnt] = {wells[i], 0, i + 1};
        }

        for(int i = 0; i < pipes.size(); ++i, ++cnt)
        {
            edges[cnt] = {pipes[i][2], pipes[i][0], pipes[i][1]};
        }

        // 跑 Kruskal 算法
        sort(edges.begin(), edges.begin() + cnt);
        int ans = 0;
        for(int i = 0; i < cnt; ++i)
        {
            // 0 : weight, 1 : u, 2 : v
            if(Union(get<1>(edges[i]), get<2>(edges[i])))
            {
                ans += get<0>(edges[i]);
            }
        }
        return ans;
    }
};